    package 哈希表;

    import java.util.NoSuchElementException;

    /**
     * 数组+链表的方式实现hash表
     */
    public class 基于开散列的方式实现的hash表 {
        private int size;//hash表的长度
        private Node[] hashtable;
        private int M;
        private final static double LOAD_FACTOR = 0.75;//负载因子
        public 基于开散列的方式实现的hash表() {
            this(16);//设置默认的hash表的长度为16
        }

        public 基于开散列的方式实现的hash表(int size) {
            this.hashtable = new Node[size];
            this.M = size;
        }

        /**
         * 对key取hash
         * @param key
         * @return 返回hash对应数组的下标值
         */
        public int hash(int key){
            return Math.abs(key) % M;
        }

        /**
         * 将node值保存道表中，或者修改node的val值
         * @param key
         * @param val
         * @return 如果key值在表中不存在，返回值为当前添加的元素的val，
         *         如果存在，put函数将原来的值修改成新的val，返回旧的val；
         */
        public int put(int key,int val) {
            int index = hash(key);//计算key对应的表中的下标位置
            //遍历hashtable[index]中的链表，查看是否存在key
            for (Node x = hashtable[index]; x != null; x = x.next) {
                if (x.key == key) {
                    int oldVal = x.val;
                    x.val = val;
                    return oldVal;//修改成功，返回修改前 的值
                }
            }
            //如果遍历index对应的链表，不存在key，采用头插法，将新的节点保存到index链表中
            Node newNode = new Node(key, val);
            newNode.next = hashtable[index];
            hashtable[index] = newNode;
            size++;
            if (size / hashtable.length >= LOAD_FACTOR){
                resize();
            }
            return val;//添加成功，返回添加后的值
            /*  例如在hash表长度为4的表中，添加[<1,10>,<2,20>,<4,40>,<5,50>]这四个元素
        1 % 4 = 1，将<1,10>保存到下标为1的位置
        2 % 4 = 2，将<2,20>保存到下标为2的位置
        4 % 4 = 0，将<4,40>保存到下标为0的位置
        5 % 4 = 1，此时发生冲突，创建一个新节点，将node(5,50)头插到index = 1的位置
        ________0________1_____________2____________3____
        |  nd(4,40)  |  nd(5,50)  |  nd(2,20)  |        |
        |            |     ↓      |            |        |
        |            |  nd(1,10)  |            |        |
        ——————————————————————————————————————————-——————
        如果是修改：比如：[<2,2000>]，那么就遍历index = 2 的链表，然后找到key = 2的节点，将节点值修改为2000
        ________0________1_____________2____________3____
        |  nd(4,40)  |  nd(5,50)  | nd(2,2000) |        |
        |            |     ↓      |            |        |
        |            |  nd(1,10)  |            |        |
        ——————————————————————————————————————————-——————
     */
        }

        /**
         * hash表的扩容长度，扩为原来的一倍
         */
        private void resize() {
            //1，创建新的数组
            Node[] newTable = new Node[hashtable.length << 1];
            //2，搬移元素
            this.M = newTable.length;
            for (int i = 0; i < hashtable.length; i++) {
                for (Node x = hashtable[i]; x != null; ){
                    Node next = x.next;//保存下一个节点
                    int index = hash(x.key);//重新极端hash表
                    //将新数组进行头插
                    x.next = newTable[index];
                    newTable[index] = x;
                    x = next;//继续把搬移原链表

                }
            }
            hashtable = newTable;
        }

        /**
         * 判断是否存在元素key
         * @param key
         * @return
         */
        public boolean containsKey(int key){
            int index = hash(key);
            for (Node x = hashtable[index]; x != null ; x = x.next){
                if (x.key == key){
                    return true;
                }
            }
            return false;
        }

        /**
         * 判断是否存在值val
         * @param val
         * @return
         */
        public boolean containsVal(int val){
            for (int i = 0; i < hashtable.length; i++) {
                for (Node x = hashtable[i]; x != null ; x = x.next){
                    if (x.val == val){
                        return true;
                    }
                }
            }
            return false;
        }

        /**
         * 判断是否存在node<k,v>
         * @param key
         * @param val
         * @return
         */
        public boolean contains(int key,int val){
            int index = hash(key);
            for (Node x = hashtable[index];x != null;x = x.next){
                if (x.val == val){
                    return true;
                }
            }
            return false;
        }

        /**
         * 删除节点
         * @param key
         * @param val
         * @return
         */
        public boolean remove(int key,int val){
            int index = hash(key);
            //如果要删除的节点就是头节点
            if (hashtable[index].key == key && hashtable[index].val == val){
                Node node = hashtable[index];
                hashtable[index] = node.next;
                node.next = node = null;
                size --;
                return true;
            }
            //如果不是头节点
            Node prev = hashtable[index];
            while (prev.next != null){
                if (prev.next.key == key && prev.next.val == val){
                    Node node = prev.next;
                    prev.next = node.next;
                    node.next = node = null;
                    size--;
                    return true;
                }
                prev = prev.next;
            }
            throw new NoSuchElementException("No search node ! remove error");
        }
    }

    /**
     * 创建一个节点类，用来实现链表，
     * 并将节点通过<k,v>的方式保存到节点数组中
     */
    class Node{
        int key;//key，对key进行hash运算，确定存储在hash表的那个坐标位置
        int val;//key对应的val；

        Node next;

        public Node() {
        }

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
